package cn.njupt.cmpSort;
//插入排序优化,利用二分查找，先找到待插入的索引，最后插入进去，相比于InsertSection2查找索引是logn级别
public class InsertionSort3<E extends Comparable<E>> extends Sort<E>{
    @Override
    public void sort() {

        for (int begin = 1; begin <array.length; begin++) {
            int insertIndex=search(begin);
            E v=array[begin];
            for(int i=begin;i>insertIndex;i--){
                array[i]=array[i-1];
            }
            array[insertIndex]=v;
        }

    }

    /**
     * 找到array[index]应该插入的位置
     * @param index 相当于二分查找中的end
     * @return
     */
    private int search(int index) {
        int left=0;
        int right=index;
        while(left<right){
            int mid=(left+right)>>1;
            if(cmp(mid,index)>0){
                right=mid;
            }else{
                left=mid+1;
            }
        }
        return left;
    }
}
